Conventional deterministic planning systems rely on a known state of the world where actions taken have a deterministic effect. One known adversarial reasoning deterministic planning system, known as Rapid Adversarial Planning with Strategic Opponent-Driven Intelligence (RAPSODI), by one or more of the inventors hereof and the inventive entity hereof, relies on analysis of deterministic adversarial problems wherein the state of the world is known and actions have deterministic effects. See e.g., U.S. patent application Ser. No. 12/198,437, entitled “Methods and Apparatus For Adversarial Planning”, filed on Aug. 26, 2008, cited supra. Uncertainty is handed off to a user, e.g., as a commander of a branch of the armed forces, such as the Army, Navy, Air Force, Marines, and the like, who selectively explores different possibilities during the planning. Such an approach achieves a very fast response for a moderately complex adversarial problem and presents the user with a “what if” sort of mission planning tool.
However, the conventional deterministic systems discussed above provide inadequate expressiveness and do not account for probabilistic actions, multiple possible worlds, and probabilistic contingencies. The term “possible world” is used in the sense of modal logic, and specifically herein refers to a description of a state of the world and a set of possible actions that entities can take in that world.
Conventional probabilistic planning systems typically include probabilistic actions and can account for one or more possible worlds. However, such systems require maintenance of a belief state for the one or more possible worlds. Planning typically generates plans that are based on the maintained belief state. However, such a design results in impractical complexities that are not tractable and thus cannot realistically be computed by currently available computer systems. The result is that conventional probabilistic planning systems cannot provide useful plans to the user.
Thus, there is a need for a hybrid probabilistic/deterministic planning system and method which is less complex, more tractable, capable of achieving a fast response, and which accommodates probabilistic actions, multiple possible worlds, and probabilistic contingencies.